{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Diagonal Traverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDiagonalOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #对角线遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的矩阵 <code>mat</code> ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/10/diag1-grid.jpg\" style=\"width: 334px; height: 334px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "<strong>输出：</strong>[1,2,4,7,5,3,6,8,9]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,2],[3,4]]\n",
    "<strong>输出：</strong>[1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= mat[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [diagonal-traverse](https://leetcode.cn/problems/diagonal-traverse/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [diagonal-traverse](https://leetcode.cn/problems/diagonal-traverse/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,5,6],[7,8,9]]', '[[1,2],[3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        sort_list = []\n",
    "        for rows in range(len(nums)):\n",
    "            for columns in range(len(nums[rows])):\n",
    "                sum = rows+columns\n",
    "                value = nums[rows][columns]\n",
    "                sort_list.append([sum,columns,value])\n",
    "        sort_list.sort()\n",
    "        for i in range(len(sort_list)):\n",
    "            ans.append(sort_list[i][2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums):\n",
    "        n = len(nums)\n",
    "        if n<=1:\n",
    "            return nums[0]\n",
    "        res = []\n",
    "        m = 0\n",
    "        for p in nums:\n",
    "            m  = max(m,len(p))\n",
    "\n",
    "        i = 0\n",
    "        while nums:\n",
    "            j = min(len(nums)-1,i)\n",
    "            while j>=0:\n",
    "                if nums[j]:\n",
    "                    res.append(nums[j].pop(0))\n",
    "                else:\n",
    "                    nums.pop(j)\n",
    "                    i -= 1\n",
    "                j -= 1\n",
    "            i += 1\n",
    "        return (res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        indexlist = [0 for i in range(len(nums))]\n",
    "        lenlist = [len(i) for i in nums]\n",
    "        res,rowindex, flag = [],0,False\n",
    "\n",
    "        while rowindex < len(nums) and not flag:\n",
    "            current_row_index = rowindex\n",
    "            flag = True\n",
    "            while current_row_index >=0:\n",
    "                if indexlist[current_row_index] <len(nums[current_row_index]):\n",
    "                    res.append(nums[current_row_index][indexlist[current_row_index]])\n",
    "                    indexlist[current_row_index] = indexlist[current_row_index] + 1\n",
    "                    flag = False\n",
    "                    current_row_index -= 1\n",
    "                else:\n",
    "                    indexlist.pop(current_row_index)\n",
    "                    nums.pop(current_row_index)\n",
    "                    rowindex -= 1\n",
    "                    current_row_index -= 1\n",
    "                \n",
    "            if rowindex < len(nums)-1:\n",
    "                rowindex += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        i=1\n",
    "        res=[]\n",
    "        nums.insert(0,[-1])\n",
    "        while True:\n",
    "            Flag=False\n",
    "            j=i\n",
    "            cnt=0\n",
    "            n=len(nums)\n",
    "            while True:\n",
    "                if nums[j] and nums[j][0]>0:\n",
    "                    # print(nums[j],j)\n",
    "                    Flag=True\n",
    "                    res.append(nums[j].pop(0))\n",
    "                if not nums[j]:\n",
    "                    \n",
    "                    nums.pop(j)\n",
    "                    cnt+=1\n",
    "                    j-=1\n",
    "                else:\n",
    "                    j-=1\n",
    "                if nums[j][0]<0:\n",
    "                    break\n",
    "            n-=cnt\n",
    "            i-=cnt\n",
    "            if i!=n-1:\n",
    "                i+=1\n",
    "            if not Flag:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        index = 0\n",
    "        ret = []\n",
    "        while len(nums) > 0:\n",
    "            del_num = 0\n",
    "            for i in range(index, -1, -1):\n",
    "                ret.append(nums[i][0])\n",
    "                nums[i] = nums[i][1:]\n",
    "                if nums[i] == []:\n",
    "                    del nums[i]\n",
    "                    del_num += 1\n",
    "            \n",
    "            index -= del_num\n",
    "\n",
    "            index += 1 if index < len(nums) -1 else 0\n",
    "            # print(ret, index)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        if max([len(x) for x in nums]) == 1:\n",
    "            return [x[0] for x in nums]\n",
    "        head = []\n",
    "        n = len(nums)\n",
    "        in_order = True\n",
    "        result = []\n",
    "        \n",
    "        def pop_back(source ,dest):\n",
    "            num = source.pop()\n",
    "            val = num.pop(0)\n",
    "            result.append(val)\n",
    "            if num:\n",
    "                dest.insert(0, num)\n",
    "        def pop_front(source, dest):\n",
    "            num = source.pop(0)\n",
    "            val = num.pop(0)\n",
    "            result.append(val)\n",
    "            if num:\n",
    "                dest.append(num)\n",
    "\n",
    "        while head or nums:\n",
    "            new_head = []\n",
    "            # print(f'head={head}, nums={nums}')\n",
    "            if nums:\n",
    "                pop_front(nums, new_head)\n",
    "            while head:\n",
    "                pop_back(head, new_head)\n",
    "            head = new_head\n",
    "\n",
    "        return result\n",
    "            \n",
    "\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        a,s,m=[(0,0)],[nums[0][0]],len(nums)\n",
    "        while a:\n",
    "            b=[]\n",
    "            for i,j in a:\n",
    "                for ii,jj in (i+1,j),(i,j+1):\n",
    "                    if ii<m and jj<len(nums[ii]) and nums[ii][jj]!=-1:\n",
    "                        s.append(nums[ii][jj])\n",
    "                        b.append((ii,jj))\n",
    "                        nums[ii][jj]=-1\n",
    "            a=b\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        q = deque()\n",
    "        q.append((0,0))\n",
    "\n",
    "        ans = []\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            ans.append(nums[i][j])\n",
    "            if j == 0 and i+1 < len(nums):\n",
    "                q.append((i+1, j))\n",
    "            if j+1 < len(nums[i]):\n",
    "                q.append((i, j+1))\n",
    "        return ans\n",
    "\n",
    "    def findDiagonalOrder1():\n",
    "        # timeout\n",
    "        m = len(nums)\n",
    "        ans = []\n",
    "        new = 1 \n",
    "        k = 0\n",
    "        while new:\n",
    "            new = 0\n",
    "            for i in range(m-1,-1,-1):\n",
    "                j = k - i\n",
    "                if 0 <= j < len(nums[i]):\n",
    "                    ans.append(nums[i][j])\n",
    "                    new += 1\n",
    "            k += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums) :\n",
    "        tot = sum([len(r) for r in nums])\n",
    "        row_next = [len(nums)] + list(range(len(nums) - 1))\n",
    "        idx_start = [0] * len(nums)\n",
    "        ans = []\n",
    "        row_start = 0\n",
    "        layer = 0\n",
    "        while len(ans) < tot:\n",
    "            \n",
    "            if idx_start[row_start] == len(nums[row_start]):\n",
    "                row_start += 1\n",
    "                continue\n",
    "            \n",
    "            row_mem = []\n",
    "            row_idx = row_start\n",
    "            while row_idx < len(nums):\n",
    "                if idx_start[row_idx] < len(nums[row_idx]):\n",
    "                    ans.append(nums[row_idx][idx_start[row_idx]])\n",
    "                    idx_start[row_idx] += 1\n",
    "                    row_mem.append(row_idx)\n",
    "                row_idx = row_next[row_idx]\n",
    "            \n",
    "            for i in range(len(row_mem) - 1):\n",
    "                row_next[row_mem[i]] = row_mem[i + 1]\n",
    "            row_next[row_mem[-1]] = len(nums)\n",
    "            \n",
    "            layer += 1\n",
    "            if len(ans) == tot:\n",
    "                break\n",
    "            if layer < len(nums) and len(nums[layer]) > 0:\n",
    "                row_start = layer\n",
    "            else:\n",
    "                for r in row_mem:\n",
    "                    if idx_start[r] < len(nums[r]):\n",
    "                        row_start = r\n",
    "                        break\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []     \n",
    "        ans = [nums[0][0]]\n",
    "        stack = [(0,0)]\n",
    "        while stack:\n",
    "            x_cur,y_cur = stack.pop(0)\n",
    "            #num = nums[x_cur]\n",
    "            for x,y in [(x_cur+1,y_cur),(x_cur,y_cur+1)]:\n",
    "                if 0<=x<len(nums) and 0<=y<len(nums[x]) and (x,y) not in stack:\n",
    "                    stack.append((x,y))\n",
    "                    ans.append(nums[x][y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        max_len = max([len(num) for num in nums])\n",
    "        if max_len == 1:\n",
    "            return [ num[0] for num in nums]\n",
    "\n",
    "        heigh = len(nums)\n",
    "        empty = 0\n",
    "        nn = 1\n",
    "        r = []\n",
    "        while True:\n",
    "            for i in reversed(range(nn-empty)):\n",
    "                r.append(nums[i].pop(0))\n",
    "                if not nums[i]:\n",
    "                    nums.pop(i)\n",
    "                    empty += 1\n",
    "            if empty == heigh:\n",
    "                return r\n",
    "            \n",
    "\n",
    "            nn = nn + 1 if nn < heigh else heigh\n",
    "        # return r\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        m = len(nums)\n",
    "        n = 0\n",
    "        nextLine = [i for i in range(0, m)]\n",
    "        for i in range(m):\n",
    "            n = max(n, len(nums[i]))\n",
    "        for i in range(m + n - 1):\n",
    "            tmp = min(m - 1, i)\n",
    "            while tmp >= 0: #[tmp][i - tmp]\n",
    "                if len(nums[tmp]) > i - tmp:\n",
    "                    res.append(nums[tmp][i - tmp])\n",
    "                    tmp = tmp - 1\n",
    "                elif tmp == 0:\n",
    "                    break\n",
    "                else:\n",
    "                    nextLine[tmp] = nextLine[tmp - 1]\n",
    "                    tmp = nextLine[tmp]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findDiagonalOrder(self, nums):\n",
    "        result, dq, col = [], collections.deque(), 0\n",
    "        for i in range(len(nums)+max(map(len, nums))-1):\n",
    "            new_dq = collections.deque()\n",
    "            if i < len(nums):\n",
    "                dq.appendleft((i, 0))\n",
    "            for r, c in dq:\n",
    "                result.append(nums[r][c])\n",
    "                if c+1 < len(nums[r]):\n",
    "                    new_dq.append((r, c+1))\n",
    "            dq = new_dq\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        m = len(nums)\n",
    "        q = [(0, 0)]\n",
    "        res = []\n",
    "        marked = [[False] * len(nums[i]) for i in range(m)]\n",
    "        while len(q) > 0:\n",
    "            curr = q.pop(0)\n",
    "            x, y = curr\n",
    "            if marked[x][y]:\n",
    "                continue\n",
    "            res.append(nums[x][y])\n",
    "            marked[x][y] = True\n",
    "            if x < m - 1 and y < len(nums[x + 1]):\n",
    "                q.append((x + 1, y))\n",
    "            if y + 1 < len(nums[x]):\n",
    "                q.append((x, y + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        x = [[0,0]]\n",
    "        out = []\n",
    "        while(len(x)>0):\n",
    "            a = x[0]\n",
    "            out.append(nums[a[0]][a[1]])\n",
    "            if a[0] + 1<len(nums) and len(nums[a[0]+1])>a[1]:\n",
    "                if [a[0]+1, a[1]] not in x:\n",
    "                    x.append([a[0]+1, a[1]])\n",
    "            if a[1] + 1<len(nums[a[0]]):\n",
    "                x.append([a[0], a[1]+1])\n",
    "            del x[0]\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        valid_row = list(range(len(nums)))\n",
    "        del_row = []\n",
    "        for epoch in range(10**6):\n",
    "            flag = False\n",
    "            for j in range(i, -1, -1):\n",
    "                true_i = valid_row[j]\n",
    "                if len(nums[true_i]) > epoch - true_i:\n",
    "                    ans.append(nums[true_i][epoch-true_i])\n",
    "                    flag = True\n",
    "                else:\n",
    "                    del_row.append(j)\n",
    "            if del_row:\n",
    "                for k in del_row:\n",
    "                    del valid_row[k]\n",
    "                    i -= 1\n",
    "                del_row = []\n",
    "            if i < len(valid_row) - 1:\n",
    "                i += 1\n",
    "            if not flag:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        retVal = []\n",
    "\n",
    "        numsSize = len(nums)\n",
    "\n",
    "        queue = deque([(0, 0)])\n",
    "        while queue:\n",
    "            row, col = queue.popleft()\n",
    "            retVal.append(nums[row][col])\n",
    "\n",
    "            if (col == 0) and (row + 1 < numsSize):\n",
    "                queue.append((row + 1, col))\n",
    "\n",
    "            numsColSize = len(nums[row])\n",
    "            if col + 1 < numsColSize:\n",
    "                queue.append((row, col + 1))\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        res=deque()\n",
    "        tovisit=[len(x) for x in nums]+[0]\n",
    "        l=len(nums)\n",
    "        layer=deque([(l,0),(0,0)])\n",
    "        nextlayer=deque([(l,0)])\n",
    "        while len(layer)>1:\n",
    "            for i,j in layer:\n",
    "                if j < tovisit[i]:\n",
    "                    res.append(nums[i][j])\n",
    "                    if nextlayer[-1] != (i+1,j):\n",
    "                        nextlayer.append((i+1,j))\n",
    "                    nextlayer.append((i,j+1))\n",
    "            layer = nextlayer\n",
    "            nextlayer = deque([(l,0)])\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.row = val\n",
    "        self.col = 0\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        over_lst = set([])\n",
    "\n",
    "        # print(len(nums))\n",
    "        # res = 0\n",
    "        # row0 = 0\n",
    "        # for lst in nums:\n",
    "        #     res += len(lst)\n",
    "        #     if len(lst) == 0:\n",
    "        #         row0 += 1\n",
    "        \n",
    "        # print(res)\n",
    "        # print(row0)\n",
    "        # return \n",
    "\n",
    "        i = 0\n",
    "        info = []\n",
    "        r, c = None, None\n",
    "        head = None\n",
    "        node = None\n",
    "        pre_node = None\n",
    "        while len(over_lst) < len(nums):\n",
    "            if i < len(nums):\n",
    "                # r = i\n",
    "                # c = 0\n",
    "                node = Node(i)\n",
    "                node.next = head\n",
    "                head = node\n",
    "            else:\n",
    "                # r = len(nums) - 1\n",
    "                # # c = 0 + (i - r)\n",
    "                # c = i - r\n",
    "                node = head\n",
    "            \n",
    "\n",
    "            i += 1\n",
    "            pre_node = None\n",
    "            while node:\n",
    "\n",
    "                r = node.row\n",
    "                c = node.col\n",
    "                if c < len(nums[r]):\n",
    "                    info.append(nums[r][c])\n",
    "                    node.col += 1\n",
    "                    pre_node = node\n",
    "                elif c == len(nums[r]):\n",
    "                    over_lst.add(r)\n",
    "                    if pre_node is None:\n",
    "                        head = head.next\n",
    "                    else:\n",
    "                        pre_node.next = node.next\n",
    "                node = node.next\n",
    "            \n",
    "        return info\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        seqs = []\n",
    "        for i, num in enumerate(nums):\n",
    "            for j, n in enumerate(num):\n",
    "                if len(seqs) < i+j+1:\n",
    "                    seqs.append([n])\n",
    "                else:\n",
    "                    seqs[i+j].append(n)\n",
    "        ans = []\n",
    "        for s in seqs:\n",
    "            ans.extend(s[::-1])\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        rows,cols = len(nums),max(len(r) for r in nums)\n",
    "        res = []\n",
    "        for r_idx,r_lst in enumerate(nums):\n",
    "            for c_idx,c_val in enumerate(r_lst):\n",
    "                res.append((r_idx+c_idx,c_idx,c_val))\n",
    "        res.sort()\n",
    "        return [v for _,_,v in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(len(nums[i])):\n",
    "                if i+j>=len(ans):\n",
    "                    ans.append([nums[i][j]])\n",
    "                else:\n",
    "                    ans[i+j].append(nums[i][j])\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(ans)):\n",
    "            res += ans[i][::-1]\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        nrow,ncol = len(nums),max([len(nums[r]) for r in range(len(nums))])\n",
    "        diag = [[] for _ in range(nrow+ncol)]\n",
    "        for r in range(nrow):\n",
    "            for c in range(len(nums[r])):\n",
    "                diag[r+c] = [nums[r][c]] + diag[r+c]\n",
    "        ans = []\n",
    "        for i in range(len(diag)):\n",
    "            ans += diag[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        group_list = []\n",
    "        for i in range(len(nums)):\n",
    "            for j, num in enumerate(nums[i]):\n",
    "                k = i + j\n",
    "                if k == len(group_list):\n",
    "                    group_list.append([])\n",
    "                group_list[k].append(num)\n",
    "        ret = []\n",
    "        for group in group_list:\n",
    "            ret.extend(group[::-1])\n",
    "        return ret        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        arr = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                if i + j >= len(arr):\n",
    "                    arr.append([])\n",
    "                arr[i+j].append(nums[i][j])\n",
    "        \n",
    "        return [v for ns in arr for v in ns[::-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        nRow = len(nums)\n",
    "        diagNums = []\n",
    "        for rowIdx in range(len(nums)):\n",
    "            curRow = nums[rowIdx]\n",
    "            for colIdx, num in enumerate(curRow):\n",
    "                diagNums.append((rowIdx + colIdx, colIdx, num))\n",
    "        diagNums.sort()\n",
    "\n",
    "        \n",
    "        \n",
    "        return [item[2] for item in diagNums]\n",
    "\n",
    "        \n",
    "'''\n",
    "find the max valid Col idx\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for i, row in enumerate(nums):\n",
    "            for j, col in enumerate(row):\n",
    "                ans.append((i + j, j, col))\n",
    "        ans.sort()\n",
    "        return list(a[2] for a in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        num_list = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                num_list.append((i + j, j, nums[i][j]))\n",
    "\n",
    "        num_list.sort()\n",
    "        return [i[2] for i in num_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "\n",
    "        queue=[(0,0)]\n",
    "        direction=[(1,0),(0,1)]\n",
    "        m=len(nums)\n",
    "        n=0\n",
    "        dn={}\n",
    "        visited=[]\n",
    "        for i in range(m):\n",
    "            dn[i]=len(nums[i])\n",
    "            n=max(n,len(nums[i]))\n",
    "            visited.append([0]*len(nums[i]))\n",
    "        visited[0][0]=1\n",
    "        result=[]\n",
    "        # print(m,n)\n",
    "        while len(queue):\n",
    "            cnt=len(queue)\n",
    "            \n",
    "            for _ in range(cnt):\n",
    "                i,j=queue.pop(0)\n",
    "                result.append(nums[i][j])\n",
    "                for di,dj in direction:\n",
    "                    # print([i+di],[j+dj])\n",
    "                    if 0<=i+di<m and 0<=j+dj<dn[i+di] and visited[i+di][j+dj]==0:\n",
    "                        visited[i+di][j+dj]=1\n",
    "                        queue.append((i+di,j+dj))\n",
    "        return result\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        M = len(nums)\n",
    "        N = max(len(nums_row) for nums_row in nums)\n",
    "\n",
    "        diag_nums = [[] for _ in range(M + N - 1)] # \n",
    "        for row_idx, row in reversed(list(enumerate(nums))):\n",
    "            for col_idx, num in enumerate(row):\n",
    "                diag = row_idx + col_idx\n",
    "                diag_nums[diag].append(num)\n",
    "        \n",
    "        ans = []\n",
    "        for diag in diag_nums:\n",
    "            ans.extend(diag)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        M = len(nums)\n",
    "        N = max(len(nums_row) for nums_row in nums)\n",
    "\n",
    "        travesed = [[] for _ in range(M + N - 1)]\n",
    "        for row_idx, row in reversed(list(enumerate(nums))):\n",
    "            for col_idx, num in enumerate(row):\n",
    "                diag = row_idx + col_idx\n",
    "                travesed[diag].append(num)\n",
    "\n",
    "        return list(itertools.chain.from_iterable(travesed))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for i,row in enumerate(nums):\n",
    "            for j,c in enumerate(row):\n",
    "                ans.append([i+j, j, c])\n",
    "                \n",
    "        ans.sort()\n",
    "        return [c[2] for c in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        q = deque([(0, 0)])\n",
    "        vis = set([(0, 0)])\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            ans.append(nums[i][j])\n",
    "            if i + 1 < n and j < len(nums[i+1]) and (newpos := (i+1, j)) not in vis:\n",
    "                vis.add(newpos)\n",
    "                q.append(newpos)\n",
    "            if j + 1 < len(nums[i]) and (newpos := (i, j+1)) not in vis:\n",
    "                vis.add(newpos)\n",
    "                q.append(newpos)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        # 遍历 nums，将元素放入对应的对角线中\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                dic[i + j].append(nums[i][j])\n",
    "        # 按照对角线的顺序构造结果列表\n",
    "        result = []\n",
    "        for k in sorted(dic.keys()):\n",
    "            # 对角线上的元素需要逆序添加到结果中\n",
    "            result.extend(dic[k][::-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        max_ind = 0\n",
    "        collector = defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                collector[i+j].append(nums[i][j])\n",
    "                max_ind = max(max_ind, i+j)\n",
    "        result = list()\n",
    "        for i in range(max_ind+1):\n",
    "            result.extend(collector[i][::-1])\n",
    "        return result\n",
    "\n",
    "    def findDiagonalOrder2(self, nums: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = list()\n",
    "        max_len = 0\n",
    "        for i, it in enumerate(nums):\n",
    "            max_len = max(max_len, len(it))\n",
    "            if len(it) > 0:\n",
    "                stack.append((i, 0))\n",
    "        for j in range(1, max_len):\n",
    "            stack.append((n-1, j))\n",
    "        result = list()\n",
    "        for i in range(len(stack)):\n",
    "            x, y = stack[i]\n",
    "            while x >= 0:\n",
    "                if len(nums[x]) > y:\n",
    "                    result.append(nums[x][y])\n",
    "                x -= 1\n",
    "                y += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        mp = defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                mp[i+j].append(j)\n",
    "        ans = []\n",
    "        for s in sorted(mp.keys()):\n",
    "            ans.extend(nums[s-j][j] for j in reversed(mp[s]))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        [\n",
    "        [(0,0),(0,1),(0,2),(0,3),(0,4)]\n",
    "        [(1,0),(1,1)]\n",
    "        [(2,0)]\n",
    "        [(3,0),(3,1),(3,2)]\n",
    "        [(4,0),(4,1),(4,2),(4,3),(4,4)]\n",
    "        ]\n",
    "        \n",
    "        解法1，可以使用bfs来完成\n",
    "\n",
    "        解法2，先是存放所有坐标值，然后再按（坐标和，纵坐标）来进行排序\n",
    "\n",
    "        \"\"\"\n",
    "        # time complexity:  O(n * m + k * logk)\n",
    "        # space complexity:  O(n * m)\n",
    "\n",
    "        result = []\n",
    "\n",
    "        for i, row in enumerate(nums):\n",
    "            for j, col in enumerate(row):\n",
    "                result.append((i+j, j, col))\n",
    "        \n",
    "        result.sort(key = lambda x: (x[0], x[1]))\n",
    "        return [i[2] for i in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 这题使用直接模拟法会超时，借鉴#498的下标排序算法\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        m = len(nums)\n",
    "        idxs = [(i, j) for i in range(m) for j in range(len(nums[i]))]\n",
    "        idxs.sort(key=lambda x:(x[0]+x[1], x[1]))\n",
    "        return [nums[i][j] for i, j in idxs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        allNums = []\n",
    "        for i, row in enumerate(nums):\n",
    "            for j, x in enumerate(row):\n",
    "                allNums.append((i, j, x))\n",
    "\n",
    "        allNums.sort(key=lambda x: (x[0] + x[1], x[1], x[0]))\n",
    "\n",
    "        return [x[2] for x in allNums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                ans.append((nums[i][j],i,j+i))\n",
    "        ans.sort(key = lambda x : (x[2],-x[1]))\n",
    "        ans = [x[0] for x in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums[i])):\n",
    "                res.append([i+j, j, nums[i][j]])\n",
    "        \n",
    "        res.sort(key=lambda x:(x[0], x[1]))\n",
    "        res = [i[2] for i in res]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "#         m = len(nums)\n",
    "#         tmp =collections.defaultdict(list)\n",
    "#         for i in range(m):\n",
    "#             n = len(nums[i]) # len()\n",
    "#             for j in range(n):\n",
    "#                 tmp[i + j].append(nums[i][j])\n",
    "#         res = []\n",
    "#         # print(sorted(tmp)) [0, 1, 2, 3, 4]\n",
    "#         for k, v in sorted(tmp.items()):\n",
    "#             res += v[::-1]\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        m = len(nums)\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(len(nums[i])):\n",
    "                dic[i + j].append(nums[i][j])\n",
    "        \n",
    "        res = []\n",
    "        for k, v in sorted(dic.items()):\n",
    "            res += dic[k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        m = len(nums)\n",
    "        result = []\n",
    "        for i in range(m):\n",
    "            for j in range(len(nums[i])):\n",
    "                result.append([i+j,j,nums[i][j]])\n",
    "        result.sort(key=lambda x:[x[0],x[1]])\n",
    "        return [num for _,_,num in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        R = len(nums)\n",
    "        dic = defaultdict(list)\n",
    "        ct = 0\n",
    "        for r in range(R):\n",
    "            C = nums[r]\n",
    "            ct += len(C)\n",
    "            for c in range(len(C)):\n",
    "                dic[r+c].append(C[c])\n",
    "        ans = []\n",
    "        for ij in range(ct+1):\n",
    "            A = dic[ij]\n",
    "            if not A: continue\n",
    "            for i in range(len(A)-1, -1, -1):\n",
    "                ans.append(A[i])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        m = len(nums)\n",
    "        left = defaultdict(list)\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(len(nums[i])):\n",
    "                left[i + j].append([i, j])\n",
    "        ans = []\n",
    "        for x in sorted(left):\n",
    "            ans.extend([nums[i][j] for i, j in left[x]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O()\n",
    "        # space: O()\n",
    "        \n",
    "        s2A = collections.defaultdict(list)\n",
    "        for i, arr in enumerate(nums):\n",
    "            for j in range(len(arr)):\n",
    "                s2A[i+j].append((i, arr[j]))\n",
    "        res = []\n",
    "        for s in sorted(s2A.keys()):\n",
    "            s2A[s].sort(reverse=True)\n",
    "            res += [v for _, v in s2A[s]]\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:\n",
    "        m = len(nums)\n",
    "        record = collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(len(nums[i])):\n",
    "                record[i+j].append([i, nums[i][j]])\n",
    "        # print(record)\n",
    "        temp = sorted(record.keys())\n",
    "        res = []\n",
    "        for key in temp:\n",
    "            cur = sorted(record[key], reverse = True)\n",
    "            for i, num in cur:\n",
    "                res.append(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        i+j\n",
    "        '''\n",
    "        max_sum=len(mat)-1+len(mat[0])-1\n",
    "        \n",
    "        idx_items = collections.defaultdict(list)\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                idx = i+j\n",
    "                idx_items[idx].append(mat[i][j])\n",
    "        res = []\n",
    "        for idx in range(max_sum+1):\n",
    "            lst = idx_items[idx]\n",
    "            if idx % 2 == 0:\n",
    "                lst = reversed(lst)\n",
    "                res += lst\n",
    "            else:\n",
    "                res += lst\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(matrix) == 0:\n",
    "            return []\n",
    "        width = len(matrix[0])\n",
    "        height = len(matrix)\n",
    "        if width == 1:\n",
    "            return [matrix[i][0] for i in range(len(matrix))]\n",
    "        edge = [i for i in range(width)]\n",
    "        for i in range(2, height + 1):\n",
    "            edge.append((width) * i - 1)\n",
    "        edge_2 = [width * i for i in range(0, height)]\n",
    "        for i in range(width):\n",
    "            edge_2.append(edge_2[-1] + 1)\n",
    "        print(edge_2)\n",
    "        ans = [matrix[0][0]]\n",
    "        for i in range(1, len(edge) - 1):\n",
    "            tmp = []\n",
    "            for j in range(edge[i], edge_2[i] + 1, width - 1):\n",
    "                x, y = self.getLoc(n=j, width=width, height=height)\n",
    "                if x < width and y < height:\n",
    "                    tmp.append(matrix[y][x])\n",
    "                else:\n",
    "                    break\n",
    "            if int(i % 2) == 0:\n",
    "                tmp.reverse()\n",
    "            ans.extend(tmp)\n",
    "        ans.append(matrix[-1][-1])\n",
    "        return ans\n",
    "\n",
    "    def getLoc(self, n, width, height):\n",
    "        x = int(n % width)\n",
    "        y = int(n / width)\n",
    "        return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def inBound(x, y, r, c):\n",
    "    return (0 <= x < c) and (0 <= y < r)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix):\n",
    "        x, y = 0, 0\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return []\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        dx, dy = 1, -1\n",
    "        ret = []\n",
    "        while True:\n",
    "            ret.append(matrix[y][x])\n",
    "            if len(ret) == cols * rows:\n",
    "                break\n",
    "            x += dx\n",
    "            y += dy\n",
    "            if not inBound(x, y, rows, cols):\n",
    "                if dx > 0:\n",
    "                    x += dx\n",
    "                    dx, dy = -1, 1\n",
    "                else:\n",
    "                    y += dy\n",
    "                    dx, dy = 1, -1\n",
    "                while not inBound(x, y, rows, cols):\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: 'List[List[int]]') -> 'List[int]':\n",
    "        #共m+n-1条对角线\n",
    "        m=len(matrix)\n",
    "        if m==0:return matrix\n",
    "        n=len(matrix[0])\n",
    "        #if n==1:return matrix\n",
    "        l=[]\n",
    "        flag=2#向右上\n",
    "        px=0;py=0\n",
    "        for i in range(0,m*n):\n",
    "            l.append(matrix[px][py])\n",
    "            if flag==1:\n",
    "                if px+1<m and py-1>=0:\n",
    "                    px+=1\n",
    "                    py-=1\n",
    "                elif px+1<m:\n",
    "                    flag=2#向右上\n",
    "                    px+=1\n",
    "                else:\n",
    "                    flag=2\n",
    "                    py+=1\n",
    "            else:\n",
    "                if px-1>=0 and py+1<n:\n",
    "                    px-=1\n",
    "                    py+=1\n",
    "                elif py+1<n:\n",
    "                    py+=1\n",
    "                    flag=1#向左下\n",
    "                else:\n",
    "                    px+=1\n",
    "                    flag=1\n",
    "        return l\n",
    "                    \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "  def findDiagonalOrder(self, matrix:List[List[int]]) ->List[int]:\n",
    "    if not matrix:\n",
    "      return []\n",
    "    row_count = len(matrix)\n",
    "    col_count = len(matrix[0])\n",
    "    nums = deque()\n",
    "    append = False\n",
    "    for start_col in range(col_count + row_count -1):\n",
    "      col = min(start_col,col_count -1)\n",
    "      row = 0 if start_col < col_count else (start_col - col_count + 1)\n",
    "      round_nums = deque()\n",
    "      while row < row_count and col > -1:\n",
    "        num = matrix[row][col]\n",
    "        if append:\n",
    "          round_nums.append(num)\n",
    "        else:\n",
    "          round_nums.appendleft(num)\n",
    "        row += 1\n",
    "        col -= 1\n",
    "      append = not append\n",
    "      nums.extend(round_nums)\n",
    "    return list(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return []\n",
    "        res = [matrix[0][0]]\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        flag = 1\n",
    "        x = y = 0\n",
    "        for i in range(1,row*col):\n",
    "            if flag == 1:\n",
    "                if x - 1 < 0:\n",
    "                    if y + 1 >= col:\n",
    "                        x += 1\n",
    "                        flag = -1\n",
    "                    else:\n",
    "                        y += 1\n",
    "                        flag = -1\n",
    "                else:\n",
    "                    if y + 1 >= col:\n",
    "                        x += 1\n",
    "                        flag = -1\n",
    "                    else:\n",
    "                        x -= 1\n",
    "                        y += 1\n",
    "            else:\n",
    "                if y - 1 < 0:\n",
    "                    if x + 1 >= row:\n",
    "                        y += 1\n",
    "                        flag = 1\n",
    "                    else:\n",
    "                        x += 1\n",
    "                        flag = 1\n",
    "                else:\n",
    "                    if x + 1 >= row:\n",
    "                        y += 1\n",
    "                        flag = 1\n",
    "                    else:\n",
    "                        x += 1\n",
    "                        y -= 1\n",
    "            res.append(matrix[x][y])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        output = []\n",
    "        if matrix == []:\n",
    "            return output        \n",
    "        x = 0\n",
    "        y = 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        total = m * n\n",
    "        for i in range(total):\n",
    "            output.append(matrix[x][y])\n",
    "            \n",
    "            if (x + y) % 2 == 0:\n",
    "                # 索引和相加为偶数.\n",
    "                if x == 0 and y != n - 1:\n",
    "                    # 在第一行, 往右边走, y + 1.\n",
    "                    y += 1\n",
    "                elif y == n - 1:  \n",
    "                    # 最后一列, 往下边走, x + 1\n",
    "                    x += 1\n",
    "                else:\n",
    "                    # 往右上走, x - 1, y + 1    \n",
    "                    x -= 1\n",
    "                    y += 1\n",
    "            else:\n",
    "                # 索引和相加为奇数.\n",
    "                if x == m - 1:\n",
    "                    # 最后一行, 往右走, y + 1\n",
    "                    y += 1\n",
    "                elif y == 0:    \n",
    "                    # 第一列, 往下走, x + 1\n",
    "                    x += 1\n",
    "                else:    \n",
    "                    # 往左下走, x + 1, y -1.\n",
    "                    x += 1\n",
    "                    y -= 1\n",
    "                    \n",
    "        return output            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        m, n, ans, inc = len(matrix), len(matrix[0]) if matrix else 0, [], [1, -1]\n",
    "        stack = [[0, 0]] if m and n else []\n",
    "        while stack:\n",
    "            for s in stack:\n",
    "                ans.append(matrix[s[0]][s[1]])\n",
    "            if inc[0] == 1:\n",
    "                if s[1] + 1 < n:\n",
    "                    stack = [[s[0], s[1] + 1]]\n",
    "                elif s[0] + 1 < m:\n",
    "                    stack = [[s[0] + 1, s[1]]]\n",
    "                else:\n",
    "                    stack = []\n",
    "            else:\n",
    "                if s[0] + 1 < m:\n",
    "                    stack = [[s[0] + 1, s[1]]]\n",
    "                elif s[1] + 1 < n:\n",
    "                    stack = [[s[0], s[1] + 1]]\n",
    "                else:\n",
    "                    stack = []\n",
    "            while stack and 0 <= stack[-1][0] + inc[0] < m and 0 <= stack[-1][1] + inc[1] < n:\n",
    "                stack.append([stack[-1][0] + inc[0], stack[-1][1] + inc[1]])\n",
    "            inc.reverse()\n",
    "            # print(stack)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        m = len(matrix)\n",
    "        if m != 0:\n",
    "            n = len(matrix[0])\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        di = -1\n",
    "        dj = 1\n",
    "\n",
    "        a = []\n",
    "\n",
    "        while m != 0:\n",
    "            a.append(matrix[i][j])\n",
    "            if i == m-1 and j == n-1:\n",
    "                break\n",
    "            if (i == 0 and j%2 == 0 and j != (n-1)) or (i == (m-1) and i%2 == 0 and j%2 == 1) or (i == (m-1) and i%2 == 1 and j%2 == 0):\n",
    "                j += 1\n",
    "                di = -di\n",
    "                dj = -dj\n",
    "            elif (i%2 == 1 and j == 0 and i != (m-1)) or (i%2 == 0 and j == (n-1) and j%2 == 0) or (i%2 == 1 and j == (n-1) and j%2 == 1):\n",
    "                i += 1\n",
    "                di = -di\n",
    "                dj = -dj\n",
    "            else:\n",
    "                i += di\n",
    "                j += dj\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: 'List[List[int]]') -> 'List[int]':\n",
    "        if not matrix:\n",
    "            return []\n",
    "        x,y = 0,0\n",
    "        xl,yl = len(matrix[0])-1,len(matrix)-1\n",
    "        v = 1\n",
    "        ret = []\n",
    "        ret.append(matrix[y][x])\n",
    "        while (x,y) != (xl,yl):\n",
    "            if y == 0 and v == 1:\n",
    "                v = -1\n",
    "                if x == xl:\n",
    "                    y+=1\n",
    "                else:\n",
    "                    x+=1\n",
    "                ret.append(matrix[y][x])\n",
    "                continue\n",
    "            if x == 0 and v == -1:\n",
    "                v = 1\n",
    "                if y == yl:\n",
    "                    x+=1\n",
    "                else:\n",
    "                    y+=1\n",
    "                ret.append(matrix[y][x])\n",
    "                continue\n",
    "            if x == xl and v == 1:\n",
    "                v = -1\n",
    "                y += 1\n",
    "                ret.append(matrix[y][x])\n",
    "                continue\n",
    "            if y == yl and v == -1:\n",
    "                v = 1\n",
    "                x += 1\n",
    "                ret.append(matrix[y][x])\n",
    "                continue\n",
    "            x += 1 if v == 1 else -1\n",
    "            y += 1 if v == -1 else -1\n",
    "            ret.append(matrix[y][x])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        steps = [[-1,1], [1,-1]]\n",
    "        if not matrix or not matrix[0]: return []\n",
    "        count, res = 0, []\n",
    "        i, j = 0, 0\n",
    "        M, N = len(matrix), len(matrix[0])\n",
    "        while len(res) < M*N:\n",
    "            if 0 <= i < M and 0<=j <N:\n",
    "                res.append(matrix[i][j])\n",
    "                step  = steps[count % 2]\n",
    "                i, j = i + step[0], j + step[1]\n",
    "                continue\n",
    "            elif i < 0 and 0 <= j < N:\n",
    "                i += 1\n",
    "            elif 0 <= i < M and j < 0:\n",
    "                j += 1\n",
    "            elif i < M and j >= N:\n",
    "                i += 2\n",
    "                j -= 1\n",
    "            elif i>= M and j < N:\n",
    "                i -= 1\n",
    "                j += 2\n",
    "            count += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        R = len(matrix)\n",
    "        C = len(matrix[0])\n",
    "\n",
    "        r,c = 0, 0\n",
    "        ret = []\n",
    "        d = [(-1, 1), (0, 1), (1, 0), (1, -1), (1, 0), (0, 1)]\n",
    "        idx = last = 0\n",
    "        while r < R and c < C:\n",
    "            if r == R - 1 and c == C - 1:\n",
    "                ret.append(matrix[r][c])\n",
    "                return ret\n",
    "            ret.append(matrix[r][c])\n",
    "            if last not in (0, 3):\n",
    "                idx = 0 if idx > 3 else 3\n",
    "            \n",
    "            ro, co = d[idx]\n",
    "            while r + ro < 0 or r + ro >= R or c + co < 0 or c + co >= C:\n",
    "                idx += 1\n",
    "                idx = idx % len(d)\n",
    "                ro, co = d[idx]\n",
    "            last = idx\n",
    "            r, c = r + ro, c + co\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        if len(matrix) == 0:\n",
    "            return []\n",
    "        else:\n",
    "            M = len(matrix)\n",
    "            \n",
    "        if len(matrix[0]) == 0:\n",
    "            return []\n",
    "        else:\n",
    "            N = len(matrix[0])\n",
    "        \n",
    "        matrix_order = []\n",
    "        \n",
    "        row = 0\n",
    "        column = 0\n",
    "        \n",
    "        while (row + column) < (M + N -1):\n",
    "            \n",
    "            matrix_order.append(matrix[row][column])\n",
    "            \n",
    "            if (row + column) % 2 == 0:\n",
    "                if column == N - 1:\n",
    "                    row += 1\n",
    "                else:\n",
    "                    column += 1\n",
    "                    row = max(row-1, 0)\n",
    "            \n",
    "            else:\n",
    "                if row == M - 1:\n",
    "                    column += 1\n",
    "                else:\n",
    "                    row += 1\n",
    "                    column = max(column-1, 0)\n",
    "        \n",
    "        return matrix_order\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''初始对角线方向为右上方（偏移量：行-1, 列+1），遇到边界时转向左下方（偏移量：行+1, 列-1）\n",
    "对于边界的处理：\n",
    "向右上方移动遇到上边界时，若未达到右边界，则向右移动（偏移量：行+0，列+1），否则向下移动（偏移量：行+1，列+0）\n",
    "向左下方移动遇到左边界时，若未达到下边界，则向下移动（偏移量：行+1，列+0），否则向右移动（偏移量：行+0，列+1）\n",
    "    '''\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix: return []\n",
    "        i,j = 0,0\n",
    "        direction = 1\n",
    "        M = len(matrix); N = len(matrix[0])\n",
    "        res = []\n",
    "        for _ in range(M*N):\n",
    "            res.append(matrix[i][j])\n",
    "            if direction>0:\n",
    "                di, dj = i-1, j+1\n",
    "            else:\n",
    "                di, dj = i+1, j-1\n",
    "            if 0<=di<M and 0<=dj<N:\n",
    "                i, j = di, dj\n",
    "            else:   # 触到边界\n",
    "                if direction>0:\n",
    "                    if j+1<N: j += 1    #未超出右边界\n",
    "                    else: i +=1\n",
    "                else:\n",
    "                    if i+1<M: i += 1    #未超出下边界\n",
    "                    else: j +=1\n",
    "                direction *= -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        M, N, result = len(matrix), len(matrix[0]), []\n",
    "        for curve_line in range(M + N - 1):\n",
    "            row_begin = 0 if curve_line + 1 <= N else curve_line + 1 - N\n",
    "            row_end = M - 1 if curve_line + 1 >= M else curve_line\n",
    "            if curve_line % 2 == 1:\n",
    "                for i in range(row_begin,row_end + 1):\n",
    "                    result.append(matrix[i][curve_line - i])\n",
    "            else:\n",
    "                for i in range(row_end,row_begin - 1,-1):\n",
    "                    result.append(matrix[i][curve_line - i])\n",
    "        return result\n",
    "        '''\n",
    "        if not matrix:\n",
    "            return []\n",
    "        ans = []\n",
    "        \n",
    "        sign,m,n = 1,len(matrix),len(matrix[0])\n",
    "        i = j = 0\n",
    "        while i != m-1 or j != n-1:\n",
    "            if sign:\n",
    "                ans.append(matrix[i][j])\n",
    "                i -= 1\n",
    "                j += 1\n",
    "                if i < 0 and j < n:\n",
    "                    i = 0\n",
    "                    sign = 0\n",
    "                    continue\n",
    "                if j == n:\n",
    "                    i += 2\n",
    "                    j -= 1\n",
    "                    sign = 0\n",
    "                    continue\n",
    "            else:\n",
    "                ans.append(matrix[i][j])\n",
    "                j -= 1\n",
    "                i += 1\n",
    "                if j < 0 and i < m:\n",
    "                    j = 0\n",
    "                    sign = 1\n",
    "                    continue\n",
    "                if i == m:\n",
    "                    j += 2\n",
    "                    i -= 1\n",
    "                    sign = 1\n",
    "                    continue\n",
    "        ans.append(matrix[i][j])\n",
    "        return ans\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        \n",
    "        \n",
    "        weight = len(matrix[0])\n",
    "        height = len(matrix)\n",
    "\n",
    "        result = []\n",
    "        tmp = []\n",
    "\n",
    "        for i in range(weight+height-1):\n",
    "            tmp.clear()\n",
    "\n",
    "            if i < weight:\n",
    "                x = i\n",
    "            else:\n",
    "                x = weight -1\n",
    "\n",
    "            if i < weight:\n",
    "                y = 0\n",
    "            else:\n",
    "                y = i - weight +1\n",
    "\n",
    "            while x >= 0 and y < height:\n",
    "                tmp.append(matrix[y][x])\n",
    "                x -=1\n",
    "                y +=1\n",
    "\n",
    "            if i % 2 == 0:\n",
    "                result.extend(tmp[::-1])\n",
    "            else:\n",
    "                result.extend(tmp)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return list()\n",
    "\n",
    "        r, l = len(matrix), len(matrix[0])\n",
    "        n, result = r + l - 1, list()\n",
    "\n",
    "        for i in range(n):\n",
    "            tmp = list()  \n",
    "            start = min(i, r - 1)\n",
    "            end = max(0, i - l + 1)\n",
    "            for x in range(start, end - 1, -1):\n",
    "                tmp.append(matrix[x][i - x])\n",
    "            if i % 2:\n",
    "                tmp = reversed(tmp)\n",
    "            result.extend(tmp)\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        li = [0]*(m*n)\n",
    "        i = 0\n",
    "        for s in range(m+n-1):\n",
    "            up = max(0,s+1-n)\n",
    "            down = min(m-1,s)\n",
    "            if s%2==0:\n",
    "                for x in range(down,up-1,-1):\n",
    "                    y = s-x\n",
    "                    li[i] = mat[x][y]\n",
    "                    i+=1\n",
    "            else:\n",
    "                for x in range(up,down+1):\n",
    "                    y = s-x\n",
    "                    li[i] = mat[x][y]\n",
    "                    i+=1\n",
    "        return li"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        length = n * m\n",
    "        result = [0] * length\n",
    "        result[0] = mat[0][0]\n",
    "        index = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        # d向下 r向右 j斜向左下 t斜向右上\n",
    "        # r j d t t d \n",
    "        flag = \"\"\n",
    "        if m == 1:\n",
    "            flag = \"d\"\n",
    "        else:\n",
    "            flag = \"r\"\n",
    "        while (index < length -1):\n",
    "            if flag == \"r\":\n",
    "                index += 1\n",
    "                j += 1\n",
    "                result[index] = mat[i][j]\n",
    "                if i == 0:\n",
    "                    flag = 'j'\n",
    "                else:\n",
    "                    flag = 't'\n",
    "                continue\n",
    "            elif flag == \"d\":\n",
    "                index += 1\n",
    "                i += 1\n",
    "                result[index] = mat[i][j]\n",
    "                if ( j != m-1 ):\n",
    "                    flag = 't'\n",
    "                elif ( j == m - 1 ):\n",
    "                    flag = 'j'\n",
    "                continue\n",
    "            elif flag == \"j\":\n",
    "                while (j != 0) and (i != n - 1):\n",
    "                    index += 1\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "                    result[index] = mat[i][j]\n",
    "                if (i != n - 1):\n",
    "                    flag = 'd'\n",
    "                elif (i == n - 1):\n",
    "                    flag = 'r'\n",
    "                continue\n",
    "            elif flag == 't':\n",
    "                while (i != 0) and (j != m - 1):\n",
    "                    index += 1\n",
    "                    i -= 1\n",
    "                    j += 1\n",
    "                    result[index] = mat[i][j]\n",
    "                if (j == m - 1):\n",
    "                    flag = 'd'\n",
    "                elif (j != m - 1):\n",
    "                    flag = 'r'\n",
    "                continue\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        mn = (m-1) + (n-1) + 1\n",
    "        ans = []\n",
    "        for i in range(mn): # 对对角线遍历\n",
    "            temp_ls = []\n",
    "            for r in range(m):# 对行遍历\n",
    "                c = i - r\n",
    "                if 0 <= c < n:# 偶数反序 奇数正序\n",
    "                    temp_ls.append(mat[r][c])\n",
    "            if i % 2 != 0:\n",
    "                ans += temp_ls\n",
    "            else:\n",
    "                ans += temp_ls[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n, ans = len(mat), len(mat[0]), []\n",
    "        for k in range(m + n - 1):\n",
    "            if not k % 2:\n",
    "                ans += [mat[x][k-x] for x in range(min(m - 1, k), max(-1, k - n),-1)]\n",
    "            else:\n",
    "                ans += [mat[x][k-x] for x in range(max(0, k - n + 1), min(k + 1, m))]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        m,n,ans=len(mat),len(mat[0]),[]\n",
    "        for count in range(m+n-1):\n",
    "            if count % 2==0:\n",
    "                x=count if count<m else m-1\n",
    "                y=count-x\n",
    "                while(x>=0 and y<=n-1):\n",
    "                    ans.append(mat[x][y])\n",
    "                    x-=1\n",
    "                    y+=1\n",
    "            else:\n",
    "                y=count if count<n else n-1\n",
    "                x=count-y\n",
    "                while(x<=m-1 and y>=0):\n",
    "                    ans.append(mat[x][y])\n",
    "                    x+=1\n",
    "                    y-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\r\n",
    "        m, n = len(mat), len(mat[0])\r\n",
    "        row, col = 0, 0\r\n",
    "        dr, dc = -1, 1\r\n",
    "        ret = []\r\n",
    "\r\n",
    "        for _ in range(m * n):\r\n",
    "            ret.append(mat[row][col])\r\n",
    "            if row + dr == m:\r\n",
    "                row = m - 1\r\n",
    "                col -= dc\r\n",
    "                dr, dc = -1, 1\r\n",
    "            elif col + dc == n:\r\n",
    "                row -= dr\r\n",
    "                col = n - 1\r\n",
    "                dr, dc = 1, -1\r\n",
    "            elif row + dr < 0:\r\n",
    "                row = 0\r\n",
    "                col += dc\r\n",
    "                dr, dc = 1, -1\r\n",
    "            elif col + dc < 0:\r\n",
    "                col = 0\r\n",
    "                row += dr\r\n",
    "                dr, dc = -1, 1\r\n",
    "            else:\r\n",
    "                row += dr\r\n",
    "                col += dc\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m+n-1):\n",
    "            if i % 2 == 0:\n",
    "                x = i if i < m else m - 1\n",
    "                y = 0 if i < m else i - m + 1\n",
    "                while x >= 0 and y < n:\n",
    "                    res.append(mat[x][y])\n",
    "                    x -= 1\n",
    "                    y += 1\n",
    "                continue\n",
    "            if i % 2 == 1:\n",
    "                x = 0 if i < n else i - n + 1\n",
    "                y = i if i < n else n - 1\n",
    "                while x < m and y >= 0:\n",
    "                    res.append(mat[x][y])\n",
    "                    x += 1\n",
    "                    y -= 1\n",
    "                continue\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        h = len(mat)\n",
    "        w = len(mat[0])\n",
    "        lists = [[] for i in range(h + w - 1)]\n",
    "        res = []\n",
    "        for i in range(h + w - 1):\n",
    "            if i < h:\n",
    "                node = [i, 0]\n",
    "                while node[0] >= 0 and node[0] < h and node[1] >= 0 and node[1] < w:\n",
    "                    lists[i].append(mat[node[0]][node[1]])\n",
    "                    node[0] -= 1\n",
    "                    node[1] += 1\n",
    "            else:\n",
    "                node = [h-1, i - h + 1]\n",
    "                while node[0] >= 0 and node[0] < h and node[1] >= 0 and node[1] < w:\n",
    "                    lists[i].append(mat[node[0]][node[1]])\n",
    "                    node[0] -= 1\n",
    "                    node[1] += 1\n",
    "            if i % 2 == 1:\n",
    "                lists[i] = lists[i][::-1]\n",
    "            res.extend(lists[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n, ans = len(mat), len(mat[0]), []\n",
    "        for k in range(m + n - 1):\n",
    "            if not k % 2:\n",
    "                ans += [mat[x][k-x] for x in range(min(m - 1, k), max(-1, k - n),-1)]\n",
    "            else:\n",
    "                ans += [mat[x][k-x] for x in range(max(0, k - n + 1), min(k + 1, m))]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        if not mat:\n",
    "            return []\n",
    "        x = y = 0\n",
    "        s = 0\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        ans = [mat[0][0]]\n",
    "        while x != n and y != m:\n",
    "            try:\n",
    "                while y > 0 and x < n-1:\n",
    "                    y -= 1\n",
    "                    x += 1\n",
    "                    ans.append(mat[y][x])\n",
    "                if x < n-1:\n",
    "                    x += 1\n",
    "                    ans.append(mat[y][x])\n",
    "                else:\n",
    "                    y += 1\n",
    "                    ans.append(mat[y][x])\n",
    "\n",
    "                while x > 0 and y < m-1:\n",
    "                    y += 1\n",
    "                    x -= 1\n",
    "                    ans.append(mat[y][x])\n",
    "                if x == 0 and y == m -1:\n",
    "                    x += 1\n",
    "                    ans.append(mat[y][x])\n",
    "                elif x > 0:\n",
    "                    x += 1\n",
    "                    ans.append(mat[y][x])\n",
    "                else:\n",
    "                    y += 1\n",
    "                    ans.append(mat[y][x])\n",
    "            except IndexError:\n",
    "                pass\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        m , n= len(mat), len(mat[0])\n",
    "        result = []\n",
    "        if not mat or not mat[0] :\n",
    "            return []\n",
    "        for t in range(m + n -1) :\n",
    "            intermediate = []\n",
    "            r = 0 if t < n else t - n + 1\n",
    "            c = t if t < n else n - 1\n",
    "            while r < m and c > -1 :\n",
    "                intermediate.append(mat[r][c])\n",
    "                r += 1\n",
    "                c -= 1\n",
    "            if (t % 2) == 0 :\n",
    "                result.extend(intermediate[::-1])\n",
    "            else :\n",
    "                result.extend(intermediate)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        m , n= len(mat), len(mat[0])\n",
    "        result = []\n",
    "        if not mat or not mat[0] :\n",
    "            return []\n",
    "        for t in range(m + n -1) :\n",
    "            intermediate = []\n",
    "            r = 0 if t < n else t - n + 1\n",
    "            c = t if t < n else n - 1\n",
    "            while r < m and c > -1 :\n",
    "                intermediate.append(mat[r][c])\n",
    "                r += 1\n",
    "                c -= 1\n",
    "            if (t % 2) == 0 :\n",
    "                result.extend(intermediate[::-1])\n",
    "            else :\n",
    "                result.extend(intermediate)\n",
    "        \n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:\n",
    "        n = len(mat)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        m = len(mat[0])\n",
    "\n",
    "        candidates = []\n",
    "        for j in range(m):\n",
    "            candidates.append((0, j))\n",
    "        for i in range(1, n):\n",
    "            candidates.append((i, m-1))\n",
    "            \n",
    "        result = []\n",
    "        for idx, candidate in enumerate(candidates):\n",
    "            row, col = candidate\n",
    "            line = [mat[row][col]]\n",
    "            while col > 0 and row < n - 1:\n",
    "                col -= 1\n",
    "                row += 1\n",
    "                line.append(mat[row][col])\n",
    "            if not (idx & 1):\n",
    "                line = line[::-1]\n",
    "            result.extend(line)\n",
    "\n",
    "        return result\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
